1. Field of the Invention
The present invention relates to a decoder which is to be utilized in the receiving end of a digital communication system for correcting symbol errors in a received digital message. In particular, the received digital message has been encoded into a group of Reed-Solomon (RS) codewords before being transmitted.
2. Description of Prior Art
In a digital data communication system which sends out digital informations through a channel to a receiver, due to noises and/or distortions, the received digital informations often contain a number of bit errors.
Referring to FIG. 1, there is shown the schematic diagram of a digital communication system which transmits digital informations in the form of words with symbols comprised of several bits. A message which is to be transmitted is first converted to a number of binary symbols, each of which has a bit length of m as shown in FIG. 2.
The digital communication system comprises a RS encoder 1 and a RS decoder 5. The symbols composing the digital information are processed by the RS encoder 1 in such a way that a number of check symbols are appended thereto to form a codeword with a block length of n. The codewords are then transmitted by a transmitter 2 via a channel 3 to a receiver 4. The RS decoder 5 is coupled to the receiver 4 and which is employed for detecting if there are symbol errors occurred in each received word and performing necessary correcting actions to the erroneous symbols.
A t-error-correcting RS codeword is often described by way of the following parameters and notations, wherein:
n denotes the block length, i.e. the number of symbols constituting one codeword; PA1 k denotes the number the information symbols in one codeword; PA1 m denotes the number of bits representing each symbol of the codeword; PA1 t denotes the maximum number of symbol errors able to be corrected; PA1 2t is the number of check symbols appended to the k information symbols, k+2t=n; PA1 d.sub.min denotes the minimum distance, d.sub.min =2t+1; PA1 C(x) denotes the polynomial of the codeword; PA1 R(x) denotes the polynomial of a received word corresponding to C(x); and PA1 E(x) denotes the polynomial of an error pattern introduced into R(x), where R(x)=C(x)+E(x). PA1 (a) calculating the syndrome values of a received word; PA1 (b) calculating the error location polynomial the syndrome values by using Euclid's algorithm; PA1 (c) determining the transform of the error polynomial; PA1 (d) inverting the transform to obtain the error polynomial. PA1 (a) calculating the syndrome values of a received word; PA1 (b) determining the error location polynomial from the syndrome values; PA1 (c) finding the roots of the location polynomial, which are used as the error locators for indicating positions where symbol errors occurred; PA1 (d) determining the error values to be used for correcting the symbol errors in accordance with the error locators. PA1 (a) determining the syndrome values of a received word; PA1 (b) utilizing an iteration method for changing the syndrome values so as to make the weight, i.e. the number of erroneous symbols, of the error pattern exactly equal to t; PA1 (c) adding in sequential order all the q-1 non-zero elements in GF(q) to the n symbol constituting the received word with testing to determine whether the weight of the error pattern has been reduced or increased. If the weight of error pattern is reduced to t-1, then both the error location and the corresponding error value are found. PA1 (d) shifting R(x) one symbol cyclically to the right and repeat step (c). PA1 (1) the method needs an iteration loop to change the syndrome values of a received word to obtain an error pattern with a weight exactly equal to t. PA1 (2) the method adds in a sequential order all the nonzero elements in GF(2.sup.m) to every symbols. That is, it requires n(k-t)+Y.sub.1 +Y.sub.2 + . . . +Y.sub.t iterations (approximately (n.multidot.k) for small t) for every received word.
The Reed-Solomon codes belong to a special subclass of non-binary BCH codes and thus the RS coding technique is suitable for application in the error correction of non-binary alphabets. With the RS coding technique, the transmission of digital information containing a stream of bits is implemented by treating a group of consecutive m bits as a symbol and n symbols as an information word.
Conventionally, a transform method is employed in a RS decoder for decoding RS codes. The transform method comprises four major steps of:
Another method, known as a standard algebraic method is also utilized in a RS decoder, which comprises the following steps of:
A step-by-step decoding method which has been proposed by Massey is still another method . The basic principle of the step-by-step decoding method for non-binary t-error-correcting BCH codes RS can be summarized as follows:
The cyclical shifting of a received word R(x) is illustrated in FIG. 3. The difference between these two algebraic methods is that the step-by-step decoding method inspects every symbol of the received word and determines thereby if the symbol under inspection is erroneous or correct; while the standard algebraic decoding method searches for the roots of an error location polynomial at first to find where symbol errors have been occurred and thereafter uses the roots for evaluating the error values needed for correcting the symbol errors.
The conventional step-by-step decoding method has two drawbacks: